package arr;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * create by yongli on 2021-07-19 16:21
 */

public class Partition {
    public static void main(String[] args) {
        int N =20;
        Integer[] a =new Integer[N];
        for(int i=0;i<N;i++){
            a[i] = i;
        }
        List<Integer>  ls = Arrays.asList(a);
        Collections.shuffle(ls);
        System.out.println(ls);

        int[] test = new int[N];
        for(int i=0;i<N;i++){
            test[i] = ls.get(i);
        }

        int par = partition(test,0,N-1);
        for(int i=0;i<N;i++){
            System.out.printf("%d ",test[i]);
        }
        System.out.println();
        System.out.println(par);
    }


    /**
     *
     * @param arr 数组
     * @param low 下限
     * @param high 上限
     * @return 返回值
     * 有点像alog4中，链表的反转
     */
    public static int partition(int[] arr,int low,int high){
        // 通过key,分成两个分部
        // 基于交换，就给你空间局促的感觉
        // 先指向一个不存在的数,是双指针的模型
        int pivot = low -1;
        int key = arr[high];

        for(int i=low;i<high;i++){
            if(arr[i]<key){
                pivot++;
                int temp = arr[i];
                arr[i] = arr[pivot];
                arr[pivot]= temp;
            }
        }

        pivot++;
        int temp = arr[pivot];
        arr[pivot] = key;
        arr[high] = temp;

        return pivot;
    }
}
